# 验证二叉搜索树：https://leetcode-cn.com/problems/validate-binary-search-tree/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        """
            中序遍历，判断， 要记录上一节点值, 定义全局变量指示是否符合要求
            看似简单的逻辑， 我竟然没想出来， 看来对全局变量（nonlocal）的应用，和 递归函数返回，还没真正能灵活运用。
        """
        pre = None
        isBST = True
        def inorder(node):
            nonlocal pre
            nonlocal isBST
            if not node: return 
            inorder(node.left)

            if pre and pre.val >= node.val:
                isBST = False
                # 终止，不再往下遍历了
                return 
            pre = node

            inorder(node.right)

        inorder(root)
        return isBST


# 官方题解中一种 前序的写法（视频中也有讲到）， 比较符合 递归子树判断为 BST的写法
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:
            if not node:
                return True
            
            val = node.val
            if val <= lower or val >= upper:
                return False

            if not helper(node.right, val, upper):
                return False
            if not helper(node.left, lower, val):
                return False
            return True

        return helper(root)

